package pri.hillchen.algorithm.string;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by hillchen on 2017/9/28 0028.
 */
public class LongestPalindrome {
    public Set<String> longestPalindrome(String source){
        if(source == null){
            return Collections.emptySet();
        }
        if("".equals(source)){
            return Collections.emptySet();
        }

        Set<String> retSets = new HashSet<String>();

        int maxPalindromeLength = 0;
        char lastChar = source.charAt(0);
        StringBuilder leftBuilder = new StringBuilder();
        StringBuilder rightBuilder = new StringBuilder();
        for(int i=1;i<source.length();i++){
            char currChar = source.charAt(i);
            int currentLength ;
            if(currChar == lastChar){
                rightBuilder.append(currChar).append(currChar);
                currentLength = createPalindrome(i-2,i+1,source,leftBuilder,rightBuilder);
                lastChar = currChar;
            }else if(i+1 < source.length() && lastChar == source.charAt(i+1) ){
                rightBuilder.append(currChar);
                currentLength = createPalindrome(i-1,i+1,source,leftBuilder,rightBuilder);
                lastChar = currChar;
            }else {
                lastChar = currChar;
                continue;
            }

            if(currentLength > maxPalindromeLength){
                maxPalindromeLength = currentLength;
                retSets.clear();
                retSets.add(connectAndEmpty(leftBuilder,rightBuilder));
            }else if(currentLength == maxPalindromeLength){
                retSets.add(connectAndEmpty(leftBuilder,rightBuilder));
            }
        }

        return retSets;
    }

    public int createPalindrome(int leftStartIndex,int rightStartIndex,String sourceStr,StringBuilder leftBuilder,StringBuilder rightBuilder){
        char c;
        while (leftStartIndex>=0 && rightStartIndex < sourceStr.length()&&(c=sourceStr.charAt(leftStartIndex))==sourceStr.charAt(rightStartIndex)){
            leftBuilder.insert(0,c);
            rightBuilder.append(c);
            leftStartIndex --;
            rightStartIndex++;
        }
        return leftBuilder.length() + rightBuilder.length();
    }
    public String connectAndEmpty(StringBuilder sb1,StringBuilder sb2){
        String ret = sb1.toString() + sb2.toString();
        sb1.setLength(0);
        sb2.setLength(0);
        return ret;
    }

    public static void main(String[] args){
        String source = "456abceecbbbbbbceecba123";
        Set<String> longestPals = new LongestPalindrome().longestPalindrome(source);
        Set<String> longestPals1 = new LongestPalindrome().longestPalindrome("aabbsxaxsbbaa  aabbsxaxs");
        for(String longestPal : longestPals){
            System.out.println(longestPal);
        }

    }
}
